/*
* 最短路径+DFS
* 道路正权无向有环图
* 航线负权有向无环图

* 边权非负 可以Dijkstra
* 拓扑图 无论边权正负 均可按照拓扑序扫描 时间复杂度是线性的

* 1.先输入所有双向道路，然后DFS出所有连通块，计算两个数组，id[]存储每个点属于哪个连通块; vector<int> block[]存储每个连通块里有哪些点
* 2.输入所有航线, 同时统计出每个连通块的入度
* 3.按照拓扑序依次处理每个连通块，先将所有入度为0的连通块的编号加入队列中
* 4.每次从队头取出一个连通块的编号bid
* 5.将该block[bid]中的所有点加入堆中, 然后对堆中所有点跑Dijkstra算法
* 6.每次取出堆中距离最小的点u
* 7.然后遍历u的所有邻点v, if id[u] == id[v] && v可以被更新 then v入堆
* 8.if id[u] ！= id[v] (即访问到有向边) id[j] 入度-1 如果减为0  则插入拓扑排序的队列中 
*/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
// #define ONLINE_GUDGE
using namespace std;
using PII = pair<int, int>;
#define x first
#define y second
const int N = 25010, M = 150010, INF = 0x3f3f3f3f;

int n, R, P, S; // T个节点 R条道路 P条航线  起点
int h[N], e[M], w[M], ne[M], idx; // 道路

int id[N];
vector<int> block[N];
int bcnt; // 连通块个数

int dist[N], din[N];
bool st[N];

queue<int> q;

void AddEdge(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

void dfs(int u, int bid)
{
    id[u] = bid;
    block[bid].push_back(u);

    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if(!id[v]) dfs(v, bid);
    }
}

void dijkstra(int bid)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for(auto v : block[bid]) heap.push({dist[v], v}) ;

    while(heap.size())
    {
        auto t = heap.top(); heap.pop();

        int u = t.y, distance = t.x;
        if(st[u]) continue;
        st[u] = true;

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                if(id[v] == id[u]) heap.push({dist[v], v});
            }

            if(id[v] != id[u] && --din[id[v]] == 0) q.push(id[v]);

        }
    }
}

void Topo()
{

    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;

    for(int i = 1; i <= bcnt; i++)
        if(!din[i]) q.push(i);

    while(q.size())
    {
        int u = q.front(); q.pop();

        dijkstra(u); // 会在dijkstra内部插入连通块, 所以需要全局队列

    }

}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> R >> P >> S; // n个节点 R条道路 P条航线  起点

    memset(h, -1, sizeof h);

    while(R--) // R条道路正权无向有环
    {
        int a, b, c; cin >> a >> b >> c;
        AddEdge(a, b, c); AddEdge(b, a, c);
    }

    for(int i = 1; i <= n; i++)
    {
        if(!id[i])
            dfs(i, ++bcnt);
    }

    while(P--) // P条航线负权有向无环
    {
        int a, b, c; cin >> a >> b >> c;
        AddEdge(a, b, c); 
        din[id[b]]++;
    }

    Topo();

    for(int i = 1; i <= n; i++)
    {
        if(dist[i] > INF / 2) printf("NO PATH\n");
        else printf("%d\n", dist[i]);
    }
    return 0;
}